
public class Main {
    public int bag(int W,int[] val,int[] weight){
        int n=weight.length;
        int[] dp=new int[W+1];
        for(int i=0;i<n;i++){
            for(int j=W;j>=weight[i];j--){
                dp[j]=Math.max(dp[j],dp[j-weight[i]]+val[i]);
            }
        }
        return dp[W];
    }

}
